/**
 * M个菜，第i个菜要用到第j个食材
 * N个食材，每个食材有一个腐烂速度b
 * 如果t时刻完成第i个菜，收益为 Ai - t * Bi, 
 * Bi为第i个菜用到的食材速度
 * 第i个菜所需时间为Ci。
 * 问T时间内所能拿到的最大值，有可能是负数
 * 
 * 首先不能直接DP，因为每个菜拿到的收益与时刻有关。
 * 考虑i、j两个菜，如果i先j后，则损失为 bi*ci + (ci + cj)*bj
 * 反之则为：bj*cj + (ci + cj)*bi
 * 因此若要i排在前面，则需要前者小，于是有 ci*bj < cj*bi
 * 只要满足这个条件，i就应该排在j前，因为损失总是小
 * 
 * 排序以后就是01背包
 * Dij = max(D[i-1][j], D[i-1][j-Ci] + Ai - j * Bi)
 * 
 * 滚动优化。注意D有可能是负的。
 * 因此将D0设为0，其余设为NINF
 */
#include <bits/stdc++.h>
using namespace std;

using llt = long long;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vi = vector<int>;
using vll = vector<llt>;


template<typename T>
void input(vector<T>&v, int n){
    v.assign(n + 1, {});
    for(int i=1;i<=n;++i) cin >> v[i];
}

template<typename T>
istream & operator >> (istream & is, vector<T> & v){
    for(auto & i : v) is >> i;
    return is;
}

llt const INF = 0x1F2F3F4F5F6F7F8F;
llt const NINF = -INF;
llt const MOD = 998244353LL;

struct _t{
    llt a, b, c;
};

int N, M, T;
vector<llt> B;
vector<_t> A;
vector<llt> D;

void work(){
    cin >> N >> M >> T;
    A.assign(M + 1, {});
    input(B, N);
    for(int t,i=1;i<=M;++i) {
        cin >> t;
        cin >> A[i].a >> A[i].c;
        A[i].b = B[t];
    }

    sort(A.begin() + 1, A.end(), [](const _t & u, const _t & v){
        return u.c * v.b < u.b * v.c;
    });

    D.assign(T + 1, NINF);
    D[0] = 0;
    for(int i=1;i<=M;++i){
        for(int j=T;j>=A[i].c;--j){
            D[j] = max(D[j], D[j - A[i].c] + A[i].a - j * A[i].b);
        }
    }
    cout << *max_element(D.begin() + 1, D.end()) << endl;
    return;
}


int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int nofkase = 1;
    // cin >> nofkase; 
    while(nofkase--) work();    
    return 0;
}
